package com.s6.sort2;

import com.s6.sort1.ArrayUtils;

/**
 * 归并排序
 */
public class MergeSort {

	public static void main(String[] args) {
		int[] array = ArrayUtils.randomInt();
		ArrayUtils.print(array);
		sort(array);
		ArrayUtils.print(array);

		array = new int[] { 1, 4, 2, 3 };
		merge(array, 0, 1, array.length - 1);
		ArrayUtils.print(array);

		array = new int[] { 1, 4, 2, 3 };
		mergeBySentry(array, 0, 1, array.length - 1);
		ArrayUtils.print(array);
	}

	public static void sort(int[] array) {
		sort(array, 0, array.length - 1);
	}

	public static void sort(int[] array, int start, int end) {
		// 终止条件：start >= end 则不用再继续分解
		if (start < end) {
			// 取 start 到 end 之间的中间位置 mid, 此处防止（start + end）的和超过 int 类型最大值
			int mid = start + (end - start) / 2;
			// 分治递归
			sort(array, start, mid);
			sort(array, mid + 1, end);
			// 将A[start...mid]和A[mid+1...end]合并为A[start...end]
			merge(array, start, mid, end);
		}
	}

	// 将两个有序的子数组合并 [start, mid] 和 [mid + 1, end]
	private static void merge(int[] array, int start, int mid, int end) {
		int[] temp = new int[end - start + 1];
		int i = start;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= end) {
			// 此处必须为 <= 才能保证排序稳定性
			if (array[i] <= array[j]) {
				temp[k] = array[i++];
			} else {
				temp[k] = array[j++];
			}
			k++;
		}
		// 将剩余的数据拷贝到临时数组
		while (i <= mid) {
			temp[k++] = array[i++];
		}
		while (j <= end) {
			temp[k++] = array[j++];
		}
		// temp 数组完全赋值给 array[start, end]
		i = 0;
		while (i < temp.length) {
			array[start++] = temp[i++];
		}
	}

	/**
	 * 合并(哨兵)
	 */
	private static void mergeBySentry(int[] array, int start, int mid, int end) {
		int[] leftTemp = new int[mid - start + 2];
		int[] rightTemp = new int[end - mid + 1];

		int i, j;
		for (i = 0; i < leftTemp.length - 1; i++) {
			leftTemp[i] = array[start + i];
		}
		// 第一个数组添加哨兵（最大值）
		leftTemp[i] = Integer.MAX_VALUE;
		for (i = 0; i < rightTemp.length - 1; i++) {
			rightTemp[i] = array[mid + 1 + i];
		}
		// 第二个数组添加哨兵（最大值）
		rightTemp[i] = Integer.MAX_VALUE;

		i = j = 0;
		// 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
		while (start <= end) {
			if (leftTemp[i] <= rightTemp[j]) {
				array[start] = leftTemp[i++];
			} else {
				array[start] = rightTemp[j++];
			}
			start++;
		}
	}

}
